§ 2.1 Field of the Invention
The present invention concerns synchronizing nodes in any environment. The present invention also concerns locating nodes in a wireless environment.
§ 2.2 Related Art
Although the node synchronization aspect of the present invention can be applied to nodes in any environment, the node location determination aspect of the present invention is particularly useful in a wireless environment. In particular, the node location determination aspect of the present invention may be applied in a wireless environment which employs spread spectrum modulation. The code division multiple access (or “CDMA”) scheme may be used in this environment. Although spread spectrum modulation is well understood by those skilled in the art, it is introduced in § 2.2.1 below for the reader's convenience. Similarly, although code division multiple access (or “CDMA”) is well understood by those skilled in the art, it is introduced in § 2.2.2 below for the reader's convenience.
§ 2.2.1 Spread Spectrum Modulation
Spread spectrum modulation modulates an already modulated signal a second time, in such a way as to generate a waveform which almost unnoticeably coexists with other signals in the same frequency band. Thus, the spread spectrum signal and other signals in the same frequency band may be said to be “transparent” to one another. More specifically, given an already modulated waveform, the spread spectrum technique further modulates this waveform so as to produce a very wideband signal.
The spread spectrum technique has been used in the military since it is difficult to detect and jam. More specifically, since the spread spectrum modulation decreases the transmit power spectral density so that it lies well below a thermal noise level, it is difficult to detect. Further, since it is difficult for a jamming signal to have sufficient power at all frequencies, a spread spectrum modulated signal is difficult to jam. In addition to historically military applications, spread spectrum modulation is now found in many commercial applications.
There are two (2) basic types of spread spectrum modulation—direct sequence (or “DS”) and frequency hopping (or “FH”). Since direct sequence spread spectrum modulation is the most applicable, it is introduced below for the reader's convenience.
A direct sequence spread spectrum signal is one in which the amplitude of an already modulated signal is amplitude modulated by a very high rate binary stream of digits. This very high rate binary stream of digits may be referred to as a pseudo-random noise (or “PN”) binary sequence having the values of ±1. The PN binary sequence is generated in a deterministic manner and is repetitive. Since the bit rate of the PN binary sequence is typically much greater than that of the modulated (e.g., data) waveform, it is often said that the PN binary sequence “chops” the bits of data into “chips”. Accordingly, the rate of the PN binary sequence may be referred to as the “chip rate”. When the PN binary sequence is used to modulate the already modulated waveform, the frequency spectrum of the already modulated waveform is spread out. More specifically, the spectrum is spread by the ratio of the frequency of the PN binary sequence to the frequency of the original signal. Similarly, power spectral density of the resulting signal is reduced by the ratio of the frequency of the original signal to the frequency of the PN binary sequence.
FIGS. 1A through 1C illustrate an original signal waveform, a PN binary sequence, and their product, respectively. FIG. 2 is a high level block diagram which illustrates a binary phase shift key (or “BPSK”) communication system incorporating a spread spectrum technique.
Having introduced the technique of spread spectrum modulation, code division multiple access (or “CDMA”) is now introduced in § 2.2.2 below.
§ 2.2.2 Code Division Multiple Access
Code division multiple access (or “CDMA”) allows each station or node of a network to transmit over the entire frequency spectrum at any time. Multiple simultaneous transmissions are separated using coding theory. As was the case with spread spectrum, in CDMA, each bit time is subdivided into a number “m” of short intervals commonly referred to as “chips”. Typically, there are 64 or 128 chips per bit. To increase the amount of information to be sent from “b” bits per second to m×b chips per second, the available bandwidth is increased by a factor of m. Thus, CDMA may be thought of as a form of spread spectrum communications.
Each station is assigned a unique m-bit code commonly referred to as a “chip sequence”. To transmit a “1” bit, a station sends its chip sequence. To transmit a “0” bit, a station sends the one's complement of its chip sequence. No other patterns are permitted. Thus, for example, if m=8 and a station is assigned 10010001 as its chip sequence, it can transmit a 1 bit by sending 10010001 and it can transmit a 0 bit by sending 01101110.
Using the symbol s to denote the m-chip vector for a station and S as it negation, the manner in which communications are divided by the chip sequence (hence the term “code division”) is explained. All chip sequences are pairwise orthogonal, which means that the normalized inner product of any two (2) distinct chip sequences is 0. This property may be expressed as follows:
                    S                  node          ⁢                                          ⁢          a                    ·              S                  node          ⁢                                          ⁢          b                      ≡                  1        m            ⁢                        ∑                      i            =            1                    m                ⁢                                  ⁢                              S            i                          node              ⁢                                                          ⁢              a                                ⁢                      S            i                          node              ⁢                                                          ⁢              b                                            =  0That is, as many pairs of the chip pattern of each station or node are the same as are different. This property of the chip sequences of the stations permits a station to recover data sent by another station, even when such data is transmitted in the presence of other transmissions.
In an ideal, noiseless CDMA system, the number of stations or nodes could be made arbitrarily large by using longer chip sequences. In practice, physical limitations reduce this capacity. For example, not all of the chips will be synchronized in time. In practice, the sender and receiver stations or nodes synchronize by having the sender transmit a long enough known chip sequence (also referred to as a “training sequence”) that the receiver can lock onto.
In view of the foregoing, it is clear that spread spectrum communications use a pseudo-noise code (PN) to “chop” bits of data into chips. Similarly, in CDMA, stations or nodes use a chip sequence to subdivide bits into chips.
§ 2.2.3 Simple Method for Synchronizing the Clocks of Two Nodes
Although the following method is presented in the background of the invention section, its inclusion here should not be construed as an admission that it is prior art to the present invention.
FIG. 3 is a flow diagram of a simple method for synchronizing the clocks of two (2) nodes, referred to below as “node A” and “node B”. As shown in block 310, node A transmits to node B (or, alternatively, broadcasts), a packet with its clock time (Ta1), as depicted by the dashed line. At node B, after the packet transmitted from node A is received, it is marked with time Tb as shown in decision block 320 and block 330. Notice that these steps may have an associated computation time. Basically, Tb will Ta1 plus the propagation delay time (k) for the transmission of the packet from node A to node B. Here, it is assumed that the computation time is negligible. Then, a packet with the times Ta1 and Tb is formed and sent from node B back to node A as shown in block 340 and depicted by the dashed line. The switch in operation of node B from a receive mode to a transmit mode may have an associated switch time. At this point, the method is done in node B as shown by END node 390.
When node A receives the packet from node B, it marks a time Ta2 as shown by decision block 350 and block 360. Node A may then adjust its clock by adding
      T    b    -                    T        a2            +              T        a1              2  to its time, thereby synchronizing its clock with the clock of node B. This can be seen from FIG. 4 which illustrates the operation of the method of FIG. 3. Since node A and B are not (necessarily) synchronized, without loss of generality, assume that the clock of node B is ahead of that of node A by s. More specifically, notice that Tb1=Ta1+k+s (+computation time which is deemed negligible). Tb2=Tb1 (+switching time which is deemed negligible). Thus, Tb2=Ta1+k+s (+computation time+switching time, each of which is deemed negligible). The time Ta2=Tb2+k−s=Ta1+k+k (+computation time+switching time, each of which is deemed negligible)=Ta1+2k (+computation time+switching time, each of which is deemed negligible). The propagation delay is therefore simply
            T      a2        -          T      a1        2(assuming that the computation and switch times are negligible). The clock at node A should be updated to the clock at node B plus the propagation delay. That is Ta2 should be set to
            T      b2        +    k    =            T      b2        +                                        T            a2                    -                      T            a1                          2            .      Since the foregoing relationship can be expressed as
            T      a2        +          T      b        -                            T          a2                +                  T          a1                    2        ,node A can update its clock merely by incrementing it by
      T    b    -                    T        a2            +              T        a1              2  as described above.
As can be appreciated from its description, the clock synchronization method of claim 3 assumes that the computation time and switching time are negligible and can be ignored. This is not always the case. Therefore, a better clock synchronization method is needed. Such a synchronization method should be independent of computation and switching times.